#pragma once
#include <iostream>
using std::make_pair;
namespace my_rbt
{
	// 红黑树 我们只掌握插入，删除暂且不做考虑
	enum COLOR
	{
		RED,
		BLACK
	};
	template <typename Val>
	struct RBNode
	{
		// 默认的颜色为什么是红色而不是黑色？
		// 默认颜色是红色在调整时，代价相对小一些
		// 默认是黑色，调整的代价比较大
		RBNode(Val kv, COLOR col = RED)
			: _left(nullptr),
			_right(nullptr),
			_parent(nullptr),
			_col(col),
			_kv(kv)

		{
		}

		RBNode<Val>* _left;
		RBNode<Val>* _right;
		RBNode<Val>* _parent;
		COLOR _col;
		// K _key;
		// V _val;
		Val _kv;
	};

	// Val -> pair<K,V>
	// map,set中的iterator 是一个双向迭代器
	// 是会提供一个 -- 的重载 --> 右根左
	// 是会提供一个 ++ 的重载 --> 左根右
	template <typename Val, typename Ptr, typename Ref>
	struct rbt_iterator
	{
		// 当上层传入的是iterator iterator 即为 iterator
		// 当上层传入的是cosnt_iterator iterato 还是 iterator
		typedef rbt_iterator<Val, Ptr, Ref> Self;
		typedef rbt_iterator<Val, Val*, Val&> iterator;

		rbt_iterator()
		{}

		rbt_iterator(RBNode<Val>* node)
			:_node(node)
		{}

		rbt_iterator(const iterator& it)
		{
			_node = it._node;
			//std::cout << "rbt_iterator(const iterator& it)" << std::endl;
		}

		// struct aa { _x ..}   paa->_x
		// 对于自定义类型 重载-> 
		Ptr operator->()
		{
			return &_node->_kv;
		}
		// 对于内置类型重载 *
		Ref operator*()
		{
			return _node->_kv;
		}

		// 中序遍历的顺序
		Self& operator++()
		{
			RBNode<Val>* right = _node->_right;
			if (right) // 右孩子存在
			{
				// 右孩子存在左子树，下一个节点为左子树上最左节点
				while (right->_left)
				{
					right = right->_left;
				}
				// 如果不存在左子树，下一个节点则为右孩子
				_node = right;
			}
			else // 右孩子不存在
			{
				// 第一个祖先是X祖先的左孩子，X祖先为下一个节点
				RBNode<Val>* parent = _node;
				RBNode<Val>* pparent = _node->_parent;
				while (pparent && pparent->_left != parent)
				{
					parent = parent->_parent;
					pparent = pparent->_parent;
				}
				if (pparent == nullptr) // 说明已经遍历完了，遍历到最后一个
					_node = nullptr;
				else
					_node = pparent;
			}
			return *this;
		}


		Self& operator--()
		{
			RBNode<Val>* left = _node->_left;
			if (left)
			{
				while (left->_right)
				{
					left = left->_right;
				}
				_node = left;
			}
			else
			{
				RBNode<Val>* parent = _node;
				RBNode<Val>* pparent = _node->_parent;
				while (pparent && pparent->_right != parent)
				{
					pparent = pparent->_parent;
					parent = parent->_parent;
				}

				if (pparent)
					_node = pparent;
				else
					_node = nullptr;
			}
			return *this;
		}

		bool operator==(const Self& s) const
		{
			return s._node == _node;
		}

		bool operator!=(const Self& s) const
		{
			return s._node != _node;
		}

		RBNode<Val>* _node;
	};

	template <typename K, typename Val, typename KeyOfVal>
	class RBTree
	{
	public:
		typedef RBNode<Val> Node;
		typedef RBTree<K, Val, KeyOfVal> Self;
		typedef rbt_iterator<Val, Val*, Val&> iterator;
		typedef rbt_iterator<Val, const Val*, const Val&> const_iterator;
	private:

		Node* get_node(Val kv, COLOR col)
		{
			return new Node(kv, col);
		}
		void LRotate(Node* cur)
		{
			Node* parent = cur->_parent;
			Node* curL = cur->_left;
			Node* pparent = parent->_parent;

			parent->_right = curL;
			if (curL)
				curL->_parent = parent;

			cur->_left = parent;
			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
					pparent->_left = cur;
				else
					pparent->_right = cur;
				cur->_parent = pparent;
			}
		}
		void RRotate(Node* cur)
		{
			Node* parent = cur->_parent;
			Node* curR = cur->_right;
			Node* pparent = parent->_parent;

			parent->_left = curR;
			if (curR)
				curR->_parent = parent;

			cur->_right = parent;
			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				_root->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
					pparent->_left = cur;
				else
					pparent->_right = cur;
				cur->_parent = pparent;
			}
		}

		int GetBlackL(Node* root)
		{
			// 这么写是获取子树上的黑色节点，而非支路上的黑色节点
			//if (root == nullptr)
			//	return 1;
			//int left = GetBlack(root->_left);
			//int right = GetBlack(root->_right);
			//int cnt = 0;
			//if (root->_col == BLACK)
			//	cnt = 1;
			//return left + right + cnt;
			int cnt = 0;
			while (root)
			{
				if (root->_col == BLACK)
					cnt++;
				root = root->_left;
			}
			return cnt;

		}
		int GetBlackR(Node* root)
		{
			int cnt = 0;
			while (root)
			{
				if (root->_col == BLACK)
					cnt++;
				root = root->_right;
			}
			return cnt;
		}
		// base：最左侧分支上 黑色节点的数目
		// pre：判断是否是二叉搜索树
		// cnt: 当前支路上的黑色节点数
		bool _IsRBTree(Node* root, int cnt, int& base, Node*& pre)
		{
			if (root == nullptr)
			{
				if (base == 0)
					cnt = base;
				else
				{
					if (cnt != base)
					{
						std::cout << "分支上黑色节点不同" << std::endl;
						return false;
					}
				}
				return true;
			}
			if (root->_col == BLACK)
				cnt++;

			if (root->_col == RED && root->_left && root->_right && !(root->_left->_col == BLACK && root->_right->_col == BLACK))
			{
				std::cout << "!(root->_left->_col == BLACK && root->_right->_col == BLACK)" << std::endl;
				std::cout << "root->_col = " << root->_col << std::endl;
				std::cout << "root->_left->_col = " << root->_left->_col;
				std::cout << " root->_right->_col = " << root->_right->_col << std::endl;
				return false;
			}


			bool left = _IsRBTree(root->_left, cnt, base, pre);
			if (pre == nullptr)
				pre = root;
			else
			{
				if (root->_kv.first <= pre->_kv.first)
				{
					std::cout << "不是二叉搜索树" << std::endl;
					return false;
				}
			}

			bool right = _IsRBTree(root->_right, cnt, base, pre);

			return left && right;
		}

		Node* _copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* node = get_node(root->_kv, root->_col);
			// 还需要建立父节点的连接
			node->_left = _copy(root->_left);
			if (node->_left)
				node->_left->_parent = node;
			node->_right = _copy(root->_right);
			if (node->_right)
				node->_right->_parent = node;

			return node;
		}

		void _destroy(Node* root)
		{
			if (root == nullptr)
				return;
			_destroy(root->_left);
			_destroy(root->_right);
			delete root;
			root = nullptr;
		}

		void _PreOrder(Node* root)
		{
			if (root == nullptr)
			{
				std::cout << "# ";

				return;
			}
			std::cout << root->_kv.first << " ";
			_PreOrder(root->_left);
			_PreOrder(root->_right);
		}

	public:
		void PreOrder()
		{
			_PreOrder(_root);
			std::cout << std::endl;
		}


		bool IsRBTree()
		{
			if (_root->_col != BLACK)
			{
				std::cout << "_root->_col != BLACK" << std::endl;
				return false;
			}
			int base = 0;
			Node* pre = nullptr;
			return _IsRBTree(_root, 0, base, pre);
		}

		std::pair<iterator, bool> insert(const Val& kv)
		{
			if (_root == nullptr)
			{
				_root = get_node(kv, BLACK);

				return make_pair(iterator(_root), true);
			}
			Node* cur = _root;
			Node* parent = cur;
			KeyOfVal kov;
			while (cur)
			{
				if (kov(kv) > kov(cur->_kv))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kov(kv) < kov(cur->_kv))
				{
					parent = cur;
					cur = cur->_left;
				}
				else
					return make_pair(iterator(cur), false);

			}
			cur = get_node(kv, RED);
			if (kov(kv) > kov(parent->_kv))
				parent->_right = cur;
			else
				parent->_left = cur;
			cur->_parent = parent;
			// 向上调节 连续红色才调整
			Node* tmp = cur;
			while (parent && parent->_col == RED)
			{
				Node* pparent = parent->_parent;
				Node* uncle = nullptr;
				if (pparent)
				{
					if (pparent->_left == parent)
						uncle = pparent->_right;
					else
						uncle = pparent->_left;
				}
				if (cur->_col == RED && parent->_col == RED)
				{
					if (uncle && uncle->_col == RED /*&& pparent->_col == BLACK*/)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						pparent->_col = RED;


						cur = pparent;
						parent = cur->_parent;
					}
					else
					{
						//     pp
						//   p
						// c
						//     p 
						//  c     pp
						if (pparent->_left == parent && parent->_left == cur)
						{
							RRotate(parent);
							cur->_col = pparent->_col = RED;
							parent->_col = BLACK;
							break;
						}
						else if (pparent->_right == parent && parent->_right == cur)
						{
							LRotate(parent);
							cur->_col = pparent->_col = RED;
							parent->_col = BLACK;
							break;

						}
						else if (pparent->_left == parent && parent->_right == cur)
						{
							LRotate(cur);
							RRotate(cur);
							pparent->_col = RED;
							parent->_col = RED;
							cur->_col = BLACK;

							break;

						}
						else if (pparent->_right == parent && parent->_left == cur)
						{
							RRotate(cur);
							LRotate(cur);
							cur->_col = BLACK;
							pparent->_col = RED;
							parent->_col = RED;
							break;

						}
					}
				}

			}
			_root->_col = BLACK;
			return make_pair(iterator(tmp), true);

		}

		std::pair<iterator, bool> find(const K& key)
		{

			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_kv.first)
					cur = cur->_right;
				else if (key < cur->_kv.first)
					cur = cur->_left;
				else
					return make_pair(iterator(cur), true);

			}
			return make_pair(iterator(nullptr), true);
		}

		iterator begin()
		{
			Node* first = _root;
			while (first && first->_left)
			{
				first = first->_left;
			}
			return iterator(first);
		}
		// 用于测试operator--
		iterator last()
		{
			Node* lt = _root;
			while (lt && lt->_right)
			{
				lt = lt->_right;
			}
			return iterator(lt);
		}
		const_iterator last() const
		{
			Node* lt = _root;
			while (lt && lt->_right)
			{
				lt = lt->_right;
			}
			return const_iterator(lt);
		}
		iterator end()
		{
			return iterator(nullptr);
		}

		const_iterator begin() const
		{
			Node* first = _root;
			while (first && first->_left)
			{
				first = first->_left;
			}
			return const_iterator(first);
		}

		const_iterator end()const
		{
			return const_iterator(nullptr);
		}


		RBTree()
		{}

		RBTree(const Self& rbt)
		{
			_root = _copy(rbt._root);
			std::cout << "RBTree(const Self& rbt)" << std::endl;

		}
		~RBTree()
		{
			_destroy(_root);
		}

		void swap(Self& rbt)
		{
			std::swap(_root, rbt._root);
		}

		RBTree(Self&& rbt)
		{
			swap(rbt);
			std::cout << "RBTree(Self&& rbt)" << std::endl;

		}
		Self& operator=(Self& rbt)
		{
			_root = _copy(rbt._root);
			std::cout << "Self& operator=(const Self& rbt)" << std::endl;
			return *this;
		}
		Self& operator=(Self&& rbt)
		{
			swap(rbt);
			std::cout << "Self& operator=(Self&& rbt)" << std::endl;
			return *this;
		}

	private:
		Node* _root = nullptr;
	};
}